CF45G Prime Problem

前置知识:哥德巴赫猜想:任一大于2的偶数都可写成两个质数之和

然后,这道题就非常水了。

S=1+2+...+nS=1+2+...+n , 我们分类讨论 SS 的情况就好了。

1.SS 为一个质数

这时将所有数加起来,分为一个区间。

2.S  0(mod  2)S~ \equiv ~0 (mod~~2)

根据哥猜,我们将 SS 分解为两个质数,分别标记。

这里有一个小结论:SS 分成的两个质数中,有一个小质数一定小于 nn

至于证明emmm...emmm...用计算机暴力吧(n6000n \le 6000)

3.S  1(mod  2)S~ \equiv ~1 (mod~~2)

(1)S2S-2为一个质数,分为两个区间:22S2S-2

(2)不然,将S3S-3 , 它是一个偶数,按情况2分解,这时需要三个区间,3 和 哥猜分出的两个质数。

#include <cstdio>

const int MAXN = 6000;
int n , sum , belong[ MAXN + 5 ];

bool zs( int x ) {
    if( x == 1 ) return 0;
    for( int i = 2 ; i * i <= x ; i ++ )
        if( x % i == 0 ) return 0;
    return 1;
}
void Make( int x ) {	//将一个数分解成两个质数之和
    for( int i = 2 ; i <= n ; i ++ )
        if( belong[ i ] == 1 && zs( i ) && zs( x - i ) ) {
            belong[ i ] = 2;
            return;
        }
}
int main( ) {
    scanf("%d",&n);
    sum = n * ( n + 1 ) / 2;
    for( int i = 1 ; i <= n ; i ++ )
        belong[ i ] = 1;
    if( zs( sum ) )
        1;
    else if( sum % 2 == 0 )
        Make( sum );
    else {
        if( zs( sum - 2 ) )
            belong[ 2 ] = 2;
        else
            belong[ 3 ] = 3 , Make( sum - 3 );
    }
    for( int i = 1 ; i < n ; i ++ )
        printf("%d ",belong[ i ]);
    printf("%d",belong[ n ]);
    return 0;
}